package com.wq.struct;

/**
 * @Author: wangqiang20995
 * @Date:2019/2/27
 * @Description:
 * @Resource:
 */
public class DoubleLinkedStruct extends Struct {

    private Node head;

    private Node tail;

    private int length;

    public DoubleLinkedStruct() {
        head = tail = new Node(-1);
        this.length = 0;
    }

    public void insertAtFirst(int number) {
        Node node = new Node(number);

        node.next = this.head.next;

        if (this.head != this.tail) {//说明链表中有节点
            this.head.next.prev = node;
        } else {
            this.tail = node;//链表一开始是空的，此时将tail指向新加入的node
        }

        node.prev = this.head;
        this.head.next = node;

        this.length++;
    }

    public void insertAtEnd(int value) {
        Node node = new Node(value);

        node.prev = tail;
        tail.next = node;

        tail = node;

        this.length++;
    }

    public void insertAtPosition(int value, int position) {
        if (position >= this.length) {
            throw new IllegalArgumentException("position[" + position + "]超出链表范围");
        }

        Node node = new Node(value);
        Node trail = head;
        for (int i = 0; i < position; i++) {
            trail = trail.next;
        }

        node.next = trail.next;
        trail.next.prev = node;

        trail.next = node;
        node.prev = trail;

        length++;
    }

    public void insertAfterNode(int target,int value){
        Node afterNode = findSpecialValue(target);

        if(afterNode == null){
            throw new IllegalArgumentException("链表中没有值为["+target+"]的node节点");
        }

        Node node = new Node(value);

        if(afterNode == tail){
            insertAtEnd(value);
        }else {
            node.next = afterNode.next;
            afterNode.next.prev = node;

            node.prev = afterNode;
            afterNode.next = node;
        }

        this.length ++;
    }

    public void deleteAtHead(){
        if(empty()){
            throw new IllegalStateException("链表为空，无法删除");
        }

        Node temp = this.head.next;
        this.head.next = temp.next;
        if(temp.next != null) {//说明节点数>1
            temp.next.prev = this.head;
        }else {
            this.tail = this.head;
        }

        this.length --;
    }

    public void deleteAtEnd(){
        if(empty()){
            throw new IllegalStateException("链表为空，无法删除");
        }

        Node delete = tail;
        Node pre = delete.prev;

        pre.next = null;//help GC
        this.tail = pre;

        length --;
    }

    public Node findSpecialValue(int value){
        if(empty()){
            return null;
        }

        Node node = head.next;//链表肯定有节点
        while (node.next != null || node == tail){
            if(node.number == value){
                break;
            }

            if(node == tail){//说明找到了tail，但是还是没有找到对应的值
                return null;
            }

            node = node.next;
        }

        return node;
    }

    public boolean empty(){
        return this.head == this.tail;
    }

    public static void main(String args[]) {
        DoubleLinkedStruct doubleLinkedStruct = new DoubleLinkedStruct();
        doubleLinkedStruct.insertAtFirst(6);
        doubleLinkedStruct.insertAtFirst(3);
        doubleLinkedStruct.insertAtFirst(2);
        doubleLinkedStruct.printStruct();

        doubleLinkedStruct.insertAtEnd(9);
        doubleLinkedStruct.printStruct();


        doubleLinkedStruct.insertAtPosition(1,2);
        doubleLinkedStruct.printStruct();

        doubleLinkedStruct.deleteAtHead();
        doubleLinkedStruct.printStruct();

        doubleLinkedStruct.deleteAtEnd();
        doubleLinkedStruct.printStruct();

        doubleLinkedStruct.insertAfterNode(1,4);
        doubleLinkedStruct.printStruct();

        doubleLinkedStruct.insertAfterNode(6,8);
        doubleLinkedStruct.printStruct();

        System.out.println(doubleLinkedStruct.findSpecialValue(0));
    }

    private class Node {

        private int number;

        private Node prev;

        private Node next;

        public Node(int number) {
            this.number = number;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "number=" + number +
                    '}';
        }
    }

    @Override
    protected void printStruct() {
        Node node = this.head.next;

        do {
            if(node != null) {
                System.out.printf("%d\t", node.number);
            }else {
                break;
            }
        } while ((node = node.next) != null);
        System.out.printf("\n");
        System.out.println("head-->" + this.head + "|tail-->" + this.tail);
    }
}
